//// leetcode.cpp: 定义控制台应用程序的入口点。
////
//
//#include <iostream>
//#include <vector>
//#include <string>
//#include <stack>
//#include <queue>
//
//using namespace std;
//
//typedef struct TreeNode
//{
//    int val;
//    struct TreeNode *left;
//    struct TreeNode *right;
//    TreeNode(int data)
//    {
//        this->val = data;
//        left = right = NULL;
//    }
//} TreeNode;
//
//
//// pre-order
//void preOrderTraversals(TreeNode* root, vector<int> &result)
//{
//    if (root == nullptr)
//        return;
//
//    result.push_back(root->val);
//    preOrderTraversals(root->left, result);
//    preOrderTraversals(root->right, result);
//}
//
//
//// in-order
//void inOrderTraversals(TreeNode * root, vector<int> &result)
//{
//    if (root == nullptr)
//        return;
//
//    inOrderTraversals(root->left, result);
//    result.push_back(root->val);
//    inOrderTraversals(root->right, result);
//}
//
//// post-order
//void postOrderTraversals(TreeNode* root, vector<int> &result)
//{
//    if (root == nullptr)
//        return;
//
//    postOrderTraversals(root->left, result);
//    postOrderTraversals(root->right, result);
//    result.push_back(root->val);
//}
//
//void BFSLevelTraversals_Top_to_Bottom(TreeNode* root, vector<int> &result)
//{
//    if (root == nullptr)
//        return;
//    queue<TreeNode*> qu;
//    qu.push(root);
//
//    while (!qu.empty())
//    {
//        TreeNode* cur = qu.front();
//        qu.pop();
//        result.push_back(cur->val);
//        if (cur->left != nullptr) qu.push(cur->left);
//        if (cur->right != nullptr) qu.push(cur->right);
//    }
//}
//
//// Level traverals  { {a}, {c,b}, {e,f} }
//void BSFLevelTraverals_Top_to_Bottom_Each_Level(TreeNode *root, vector<vector<int>> &result)
//{
//    if (root == nullptr)
//        return;
//
//    queue<TreeNode*> qu;
//    qu.push(root);
//
//    while (!qu.empty())
//    {
//        int cursize = qu.size();
//        result.push_back(vector<int>());
//
//        for (int i = 0; i < cursize; i++) {
//
//            TreeNode* cur = qu.front();
//            qu.pop();
//            result.back().push_back(cur->val);
//            if (cur->left != nullptr)
//            {
//                qu.push(cur->left);
//            }
//            if (cur->right != nullptr)
//            {
//                qu.push(cur->right);
//            }
//        }
//    }
//    cout << endl;
//
//    // reverse result bottom to up
//    // std::reverse(result.begin(), result.end());
//}
//
//void LevelTraversals_Bottom_To_Top(TreeNode* root, vector<vector<int>> &result)
//{
//    BSFLevelTraverals_Top_to_Bottom_Each_Level(root, result);
//    std::reverse(result.begin(), result.end());
//}
//
//
//// leetcode 104:最大深度=树的高度
//int GetTreeHeight(TreeNode* root)
//{
//    if (root == nullptr)
//        return 0;
//    // framework
//    int lheight = GetTreeHeight(root->left);
//    int rheight = GetTreeHeight(root->right);
//
//    return max(lheight, rheight) + 1;
//}
//
//// leetcode 111:最小深度
//int minDepth(TreeNode* root)
//{
//    if (root == nullptr)
//        return 0;
//    // 1.
//    if (root->right == nullptr && root->left == nullptr)
//        return 1;
//
//    // 2.
//    int leftdepth = minDepth(root->left);
//    int rightdepth = minDepth(root->right);
//
//    // leftdepth 或者 rightdepth 一定有一个0，所以直接相加即可
//    if (root->left == nullptr || root->right == nullptr)
//        return leftdepth + rightdepth + 1;
//
//    // 3.
//    return min(leftdepth, rightdepth) + 1;
//}
//
//// BFS get depth
//// 广度优先遍历
//int bfsGetDepth(TreeNode* root)
//{
//    if (root == nullptr)
//        return 0;
//
//    queue<pair<TreeNode*, int>> que;
//
//    que.emplace(root, 1);
//    while (!que.empty())
//    {
//        TreeNode* node = que.front().first;
//        int depth = que.front().second;
//        que.pop();
//        if (node->right == nullptr && node->left == nullptr)
//        {
//            return depth;
//        }
//        if (node->left != nullptr)
//        {
//            que.emplace(node->left, depth + 1);
//        }
//        if (node->right != nullptr)
//        {
//            que.emplace(node->right, depth + 1);
//        }
//    }
//    return 0;
//}
//
//// leetcode 104:最大深度=树的高度
//int maxDepth(TreeNode * root)
//{
//    if (root == nullptr)
//        return 0;
//
//    int leftdepth = maxDepth(root->left);
//    int rightdepth = maxDepth(root->right);
//
//    return max(leftdepth, rightdepth) + 1;
//}
//
//void findLeaves(TreeNode* root, vector<int> &result)
//{
//    if (root == nullptr)
//        return;
//    findLeaves(root->left, result);
//    findLeaves(root->right, result);
//    if (root->left == nullptr && root->right == nullptr)
//        result.push_back(root->val);
//}
//
//// https://leetcode-cn.com/problems/find-leaves-of-binary-tree/
//// 366. 寻找二叉树的叶子节点
//// 求最大深度或者高度的时候演变而来
//// 迭代过程，做逻辑处理
//int findLeavesAndRemove(TreeNode* root, vector<vector<int>> &result)
//{
//    if (root == nullptr)
//        return 0;
//    int left = findLeavesAndRemove(root->left, result);
//    int right = findLeavesAndRemove(root->right, result);
//
//    int level = max(left, right) + 1;
//    if (result.size() < level)
//    {
//        result.push_back(vector<int>());
//    }
//    result[level - 1].push_back(root->val);
//    return level;
//}
//
//// 二叉搜索树的性质;中序遍历为升序
//bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max)
//{
//    if (root == nullptr)
//        return true;
//    if (min != nullptr && root->val <= min->val)
//        return false;
//    if (max != nullptr && root->val >= max->val)
//        return false;
//    return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
//}
//
//void printVector(string notes, vector<int> &result)
//{
//    vector<int>::iterator iter = result.begin();
//    cout << notes;
//    for (; iter != result.end(); iter++)
//    {
//        cout << *iter << " ";
//    }
//    cout << endl;
//}
//
//void printVectorVector(string notes, vector<vector<int>> &result)
//{
//    vector<vector<int>>::iterator iter = result.begin();
//    cout << notes << "\n{\n";
//    for (; iter != result.end(); iter++)
//    {
//        vector<int>::iterator subiterbegin = (*iter).begin();
//        vector<int>::iterator subiterend = (*iter).end();
//        cout << "{";
//        for (; subiterbegin != subiterend; subiterbegin++)
//        {
//            cout << *subiterbegin << ",";
//        }
//        cout << "}\n";
//    }
//    cout << "}\n" << endl;
//}
//
//int mysimplemain()
//{
//    std::cout << "Hello world" << std::endl;
//
//    TreeNode *root = new TreeNode(1);
//    root->left = new TreeNode(2);
//    root->right = new TreeNode(3);
//    root->left->left = new TreeNode(4);
//    root->left->right = new TreeNode(5);
//
//    vector<int> vectorResult;
//    inOrderTraversals(root, vectorResult);
//    printVector("inorder:", vectorResult);
//
//    vectorResult.clear();
//    preOrderTraversals(root, vectorResult);
//    printVector("preoder:", vectorResult);
//
//    vectorResult.clear();
//    postOrderTraversals(root, vectorResult);
//    printVector("postorder:", vectorResult);
//
//    vectorResult.clear();
//    BFSLevelTraversals_Top_to_Bottom(root, vectorResult);
//    printVector("levelorder top to bottom:", vectorResult);
//
//    vectorResult.clear();
//    findLeaves(root, vectorResult);
//    printVector("find leaves:", vectorResult);
//
//    vector<vector<int>> levelresult;
//    root->right->left = new TreeNode(6);
//    root->right->right = new TreeNode(7);
//    root->left->left->left = new TreeNode(8);
//    BSFLevelTraverals_Top_to_Bottom_Each_Level(root, levelresult);
//    printVectorVector("each level order top to bottom:", levelresult);
//
//    levelresult.clear();
//    int maxDepth = findLeavesAndRemove(root, levelresult);
//    cout << "maxdepth:" << maxDepth << endl;
//    printVectorVector("find leaves:", levelresult);
//
//
//    // 二叉搜索树
//    TreeNode *bstroot = new TreeNode(5);
//    bstroot->left = new TreeNode(1);
//    //bstroot->left->left = new TreeNode(0);
//    bstroot->right = new TreeNode(4);
//    bstroot->right->left = new TreeNode(3);
//    bstroot->right->right = new TreeNode(6);
//
//    bool validBST = isValidBST(bstroot, nullptr, nullptr);
//
//    cout << "You are what U do" << endl;
//    return 0;
//}
//
//
//// 树算法：
///*
// 559 : N叉树的最大深度
// 104 : 最大深度=树的高度
// 111 : 最小深度
// 589. N 叉树的前序遍历(递归和非递归形式)
//
// 标记法实现nullptr 注意需要"逆序"处理
// rbegin,rend
// 1. 前序-> 右左中
// 2. 中序-> 右中左
// 3. 后序-> 中右左
//
// pre-order,in-order,post-order(traversals with recursion and without recursion)
//
// 层序遍历(bottom-up,up-bottom)，针对up-bottom做一次vector翻转
//
//
// */
